#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int f[50005][50];
int fm[50005][50];
int log_2[50005];
int main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>f[i][0];
        fm[i][0]=f[i][0];
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            fm[i][j]=min(fm[i][j-1],fm[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=2;i<=n;i++){
        log_2[i]=log_2[i>>1]+1;
    }
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        int x=log_2[b-a+1];
        cout<<max(f[a][x],f[b-(1<<x)+1][x])-min(fm[a][x],fm[b-(1<<x)+1][x])<<endl;
    }
    return 0;
}